package com.samxcode.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given a collection of numbers, return all possible permutations.
 * 
 * For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1],
 * [3,1,2], and [3,2,1].
 * 
 * solution:
 * NP problem
 * backtracking, recursion
 * http://blog.csdn.net/linhuanmars/article/details/21569031
 * 迭代法，相当于逐个插入每个list的每一个位置，也可以转化为树的形式
 * http://blog.csdn.net/tuantuanls/article/details/8717262
 * @author Sam
 *
 */
public class Permutations {
    
    public static void main(String[] args) {
        Integer[] nums = {1, 2, 3, 5};
        System.out.println(permute1(nums));
    }
    

    public static List<List<Integer>> permute1(Integer[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        List<Integer> list = new ArrayList<Integer>();
//        list.add(nums[0]);
        helper1(res, new ArrayList<>(Arrays.asList(nums)), list);
        return res;
    }
    
    
    private static void helper1(List<List<Integer>> res, List<Integer> item, List<Integer> item1) {
        if (item.isEmpty()) {
            res.add(new ArrayList<>(item1));
        }
        for (int i = 0; i < item.size(); i++) {
            List<Integer> temp = new ArrayList<>(item);
            List<Integer> temp1 = new ArrayList<>(item1);
            temp1.add(temp.get(i));
            temp.remove(i);
            helper1(res, temp, temp1);
        }
    }


    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        helper(res, new ArrayList<>(), new boolean[nums.length], nums);
        return res;
    }


    private static void helper(List<List<Integer>> res, List<Integer> item, boolean[] used, int[] nums) {
        if (item.size() == nums.length) {
            res.add(new ArrayList<>(item));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                item.add(nums[i]);
                helper(res, item, used, nums);
                item.remove(item.size() - 1);
                used[i] = false;
            }
        }
    }


    public static List<List<Integer>> permuteIterator(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        List<Integer> first = new ArrayList<>();
        first.add(nums[0]);
        res.add(first);
        for (int i = 1; i < nums.length; i++) {
            List<List<Integer>> newRes = new ArrayList<>();
            for (int j = 0; j < res.size(); j++) {
                List<Integer> cur = res.get(j);
                for (int k = 0; k <= cur.size(); k++) {
                    List<Integer> item = new ArrayList<>(cur);
                    item.add(k, nums[i]);
                    newRes.add(item);
                }
            }
            res = newRes;
        }
        return res;
    }
}
